package algorithms.graph;

/**
 * 检验图G是不是无环图
 * @author glogo
 *
 */
public class Cycle {

	private boolean[] marked;
	private boolean hasCycle;
	
	public Cycle(Graph g) {
		marked = new boolean[g.V()];
		//需要对图中的每一个连通分量进行判断
		for(int s = 0; s < g.V(); s++){
			if(!marked[s])
				dfs(g, s, s);
		}
	}
	
	//u其实是起记录上一个节点的作用
	private void dfs(Graph g, int v, int u){
		marked[v] = true;
		for(int w : g.adj(v)){
			if(!marked[w])	dfs(g, w, v);
			else if(w != u) hasCycle = true;
		}
	}
	
	public boolean hasCycle(){
		return hasCycle;
	}
	
}
